1. Field of the Invention
The invention relates to a method for the generation of digital signatures for electronic messages.
The method can be applied especially to the signing of messages by portable devices of the microprocessor-based smart card type.
For example, it may be necessary to sign messages sent by the card to a reading terminal or to a central authority. Or again, it may be necessary to carry out a transaction (an electronic cheque transaction) and to sign this transaction so that it can be authenticated first of all by the reading terminal in which the transaction is made and then by a central authority that manages the transaction.
The method that shall be described is related to the algorithms for the generation of digital signatures published in recent years, especially by the U.S. National Institute of Standards and Technology, for example the DSA (Digital Signature Algorithm) described in the U.S. patent application Ser. No. 07/736451 filed Jul. 26, 1991 and now U.S. Pat. No. 5,231,668 and published on the 30the of Aug. 1991 in the Federal Register kept by this Institute, pages 42980-42982.
The invention is aimed at modifying the known methods, in particular to make them adaptable to microprocessor-based cards that do not have physical resources (processor, memories) sufficient to swiftly carry out mathematical operations on big numbers. The known algorithms, especially the DSA, use big numbers to generate signatures with a sufficient degree of security.
2. Description of the Related Art
In order to provide for a clear understanding of the invention, first of all a reminder shall be given of what is the DSA algorithm.
A DSA signature consists of a pair {r, s} of big numbers represented in computers by long strings of binary digits (160 digits). The digital signature is computed by means of a series of computation rules defined by the algorithm and a set of parameters used in these computations. The signature enables both the certifying of the identity of the signer (because it brings into action a secret key proper to the signer) and the integrity of the signed message (because it brings into action the message itself). The algorithm makes it possible firstly to generate signatures and secondly to check signatures.
The generation of DSA signatures brings into action a secret key. The check brings into action a public key that corresponds to the secret key but is not identical to it. Each user has a pair of keys (secret, public). The public keys may be known to all while the secret keys are never revealed. Anybody has the capacity to check the signature of a user by using the public key of this user but only the possessor of the secret key can generate a signature corresponding to the pair of keys.
The parameters of the DSA are the following:
a prime number p such that 2.sup.L-1 &lt;p 2.sup.L for L ranging from 512 to 1024 (including the limits) and L=64a for a as any integer; PA1 a prime number q such that 2.sup.159 &lt;q 2.sup.160 and p-1 is a multiple of q; PA1 a number g, q order modulo p, such that: PA1 a randomly or pseudo-randomly generated number x (this is the secret key, fixed for a given user); PA1 a number y defined by the relationship PA1 a randomly or pseudo-randomly generated number k such that 0&lt;k&lt;q. PA1 r=(g.sup.k mod p) mod q, and PA1 s=(m +xr)/k mod q PA1 (where the division by k is taken to be modulo q, namely that 1/k is the number k' such that kk'=1 mod q; for example if q=5 and k=3, then 1/k=2 for 3.times.2=6, giving 1 mod 5). PA1 a. w=(1/s) mod q PA1 b. u1=mw mod q PA1 c. u2=rw mod q PA1 d. v=g.sup.u1 .multidot.y.sup.u2 mod p! mod q PA1 v=f(r.sub.i, s)=r.sub.i PA1 this method being characterized in that: PA1 the coupons are compressed by the application of a compression function, also called a hash function, by a certified authority before being loaded into the memory, and in that this method comprises the following exchanges:
g=h.sup.(p-l)/q modulo p where h is any integer checking PA2 1&lt;h&lt;p-1 and g&gt;1; PA2 y=g.sup.x modulo p; (this is the public key linked to the secret key); the modular operations defined here below, modulo p or modulo q, shall be designated by mod p or mod q respectively; PA2 a. the signature coupon is established in advance by a certified authority, in two steps: PA2 b. a series of different coupons of small length are thus prepared in advance and stored in the signer unit (smart card with memory and microprocessor), PA2 c. the signature generation comprises the sending of a coupon r.sub.i and a signature complement s computed on the basis of at least r.sub.i and x, PA2 d. the signature checking algorithm comprises a mathematical computation followed by the same complex compression function as the one used to prepare the coupon, and the result is compared with the coupon for the signature check. PA2 a message m is transmitted and this message must be certified by a signature, PA2 the signer sends a coupon r.sub.i to the verifier, PA2 the verifier sends a random number a to the signer and activates a timer, PA2 the signer computes the signature s of the message and sends it to the verifier, PA2 the verifier stops the timer and ascertains that the signature has been obtained through the secret held in the card and the coupon r.sub.i received; this checking is done by checking the following equality: EQU v=f(r.sub.i, s, m)=r.sub.i PA2 the verifier accepts the signature if the condition of checking v=r.sub.i is fulfilled and if the measured time does not exceed an allocated predetermined period.
The integers p, q and g are parameters of the system that can be published and/or shared by a group of users. The secret and public keys of a signer are respectively x and y. The parameter k which is a random parameter must be regenerated for each new signature. The parameters x and k are used for the generation of signatures and must be kept secret.
In order to sign a message m (which will generally be a hashed value of an initial file M), the signer computes the signature {r, s} by:
After the fact that r and s are different from zero has been tested, the signature {r, s} is sent to the verifier. The verifier is generally the terminal into which the smart card that sends the message m and the signature {r, s} is inserted.
The verifier, which knows p, q, g (related to the application), y (related to the user) and m (the message that he has received from the card), computes:
Now, this value g.sup.u1.y.sup.u2 mod p! mod q is precisely equal to r if s has the value (m+xr)/s mod q.
Consequently, the terminal receives r and s and ascertains that v is really equal to r to accept the signature or reject it otherwise.
Hereinafter, the term "signer" or signer unit or proving device or smart card shall be used without distinction to designate the device that sends out the signature and that will generally be a smart card. And the term "verifier" or verifier unit or verifier device or verifier terminal or again control authority shall be used without distinction to designate the device that receives the signature and checks it to accept or reject a transaction or a message. The simplest application of the invention is the sending of the signature by means of a smart card to a reading terminal into which the card is inserted, with the terminal performing the checking function and being connected or not connected to a central management authority.